package cn.zyl.demo.java.sort;

/**
 * HeapSort  类说明: 堆排序
 * ---------------------------------------------------------------------
 * <p>堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点</p>
 * <p>堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：</p>
 * <p>大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；</p>
 * <p>小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；</p>
 * <p>堆排序的平均时间复杂度为 Ο(n log n)</p>
 * @author wsz
 * @version v1.0
 * @date 2020-08-13
 */
public class HeapSort extends AbstractArraySortSimple{
    /**
     * 排序接口
     * <pre>
     *     算法步骤:
     *     1.将待排序序列构建成一个堆 H[0……n-1]，根据（升序降序需求）选择大顶堆或小顶堆；
     *     2.把堆首（最大值）和堆尾互换；
     *     3.把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
     *     4.重复步骤 2，直到堆的尺寸为 1。
     * </pre>
     * @param sourceArray 待排序数组
     * @param order       排序方式，(默认)升序 true；降序 false
     * @return 排序后的数组
     * @throws Exception 异常信息
     */
    @Override
    public Integer[] sort(Integer[] sourceArray, Boolean order) throws Exception {
        int len = sourceArray.length;
        Integer[] arr = copyArray(sourceArray,len);
        start();
        buildMaxHeap(arr, len,order);
        for(int i = len - N_1 ; i > 0 ; i-- ){
            addOne();
            swapValBit(arr, N_0, i);
            len --;
            heapIfy(arr, 0, len,order);
        }
        end();
        return arr;
    }
    /** 建立大/小顶堆*/
    private void buildMaxHeap(Integer[] arr,int len, Boolean order){
        for(int i = (int)Math.floor(len/N_2) ; i >= 0 ; i--){
            heapIfy(arr, i, len,order);
        }
    }
    /** 堆调整*/
    private void heapIfy(Integer[] arr, int i, int len, Boolean order){
        int left = N_2 * i +N_1;
        int right = N_2 * i +N_2;
        int largest = i;
        if(order){
            //大顶堆
            if(left < len && arr[left] > arr[largest]){ largest = left; }
            if(right < len && arr[right] > arr[largest]){ largest = right; }
        }else {
            //小顶堆
            if(left < len && arr[left] < arr[largest]){ largest = left; }
            if(right < len && arr[right] < arr[largest]){ largest = right; }
        }
        if(largest != i){
            addOne();
            swapVal(arr, i, largest);
            heapIfy(arr, largest, len,order);
        }
    }
    public static void main(String[] args) {
        int len =15,max=100;
        //待排序数组初始化
        Integer[] arr = randomArray(len,max);
        AbstractArraySortSimple sort = new HeapSort();
        try {
            System.out.println("升序操作");
            printArray(sort.sort(arr, true));
            System.out.println("降序降序");
            printArray(sort.sort(arr, false));
        }catch (Exception e){
            e.printStackTrace();
        }
    }
}
